NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/7831

Text File | 1996-08-05 | 2.9 KB | 93 lines

Path: camelot.dsccc.com!not-for-mail
From: [e-mail] (Kevin Cline)
Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
Subject: Re: Tough FACTORIAL math problem...
Date: 19 Feb 1996 11:14:02 -0600
Organization: DSC Communications Corporation Switch Products Division
Message-ID: <4gab4q$[e-mail]>
References: <4fr8be$[e-mail]> <4g0giv$[e-mail]> <[e-mail]>
NNTP-Posting-Host: sun152.spd.dsccc.com

In article <[e-mail]>, Dik T. Winter <[e-mail]> wrote:
>[Note: at the end there is a complete explanation of the problem and the
>solution.  At first here follows a flamelet.]
>
>[stuff previousl posted by me deleted]
>But you did it only halfway, see below.

Right; I did miss a key point, but my instinct that there was a O(log n)
solution was correct.

>bugs in my first posting exposed...
>
>Did you try your function?
>
Well no.

>Using only the last k digits of the factorial (excluding trailing zeros)
>and the last l digits of the multiplier will ultimately lead to a
>period.  (The proof is fairly simple.)  But the last non-zero digit of
>the factorial does not show a period; the increasing number of factors 5
>that can occur in a single number prevent this.  So, all such methods
>will fail at some stage.  Taking care of all individual factors 5 solves
>this.
>

Sure, but there is a much quicker and easier way to do this.  Thanks for
pointing me down the correct path.  Here is the definitive solution,
which runs in O(log n) time and can compute the last non-zero digit of
the factorial of any number up to INT_MAX in a few milliseconds.  This
code has been check against 1!-20! and a few elements from Dik's table
that were easy to spot, like 900, 901, 950, 951, 1000

Basically, the idea is:

27! = (26x27)x(1x2x3x4)x(6x7x8x9)x(11x12x13x14)x(16x17x18x19)x(21x22x23x24)
    x(5x5x5x5x5)x(1x2x3x4x5)

Each number in the list moves some number of places through the cycle
6,2,4,8.  Each set 1-4 or 6-9 moves two places to the right.
Each 5 moves one place to the left.  The stuff left over after dividing
one 5 from each multiple of 5 is just another factorial, so we can
solve this quickly with a recursive function, as follows:

#include <iostream.h>
#include <stdlib.h>

// last digits of powers of two
static int t0[] = { 6, 2, 4, 8 };

// log base two (mod 5) of 0! - 4!
static int t1[] = { 0, 0, 1, 0, 2 } ;

static int f(int i) {
  if (i == 0) return 0;
  return t1[i % 5] + i/5 + f(i/5);
}

static int lastNonZeroDigitOfFactorial(int i) {
  if (i < 2) return 1;
  return t0[f(i) % 4];
}

int main(int argc, char **argv) {
  if (argc < 2) {
    cout << "usage: " << argv[0] << " n\n";
    exit(1);
  }

  int i = atoi(argv[1]);
  if (i < 0) {
    cout << argv[0] << ": non-negative argument required\n";
    exit(1);
  }

  cout << "The last non-zero digit of " << i << "! is "
       << lastNonZeroDigitOfFactorial(i) << endl;
}



--
Kevin Cline